package com.Dec_Eleven;

import java.util.ArrayList;
import java.util.List;

/**
 * 763. 划分字母区间
 * 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
 * https://leetcode.cn/problems/partition-labels/
 *
 * 2022/11/11 08:48
 */

public class Solution763 {

    /**
     * 可以作图分析
     * @param s
     * @return list
     */
    public List<Integer> partitionLabels(String s) {
        int[] words=new int[26];
        int len=s.length();
        for (int i = 0; i < len; i++) {
            words[s.charAt(i)-'a']=i;
        }
        List<Integer> list=new ArrayList<>();
        int start=0,end=0;
        for (int i = 0; i < len; i++) {
            end=Math.max(end,words[s.charAt(i)-'a']);
            if (i==end) {
                list.add(end-start+1);
                start=end+1;
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Solution763 solution763=new Solution763();
        System.out.println(solution763.partitionLabels("ababcbacadefegdehijhklij"));
    }
}
